package j2024.j202411;

public class j1111 {
    /**
     * 530. 二叉搜索树的最小绝对差
     * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     *
     * 差值是一个正数，其数值等于两值之差的绝对值。
     */
    int ret = Integer.MAX_VALUE;
    int pre = -1;
    public int getMinimumDifference(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root);
        return ret;
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(pre == -1){
            pre = root.val;
        }else {
            ret = Math.min(ret,root.val-pre);
            pre = root.val;
        }
        dfs(root.right);
    }

    /**
     * 230. 二叉搜索树中第 K 小的元素
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
     */
    int smallret;
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs1(root);
        return smallret;
    }
    public void dfs1(TreeNode root){
        if(root == null|| count==0){
            return;
        }
        dfs1(root.left);
        if(count==0) return;
        count--;
        smallret = root.val;
        if(count==0) return;
        dfs1(root.right);
    }

    /**
     * 98. 验证二叉搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     *
     * 有效 二叉搜索树定义如下：
     *
     * 节点的左
     * 子树
     * 只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     */
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        boolean left = isValidBST(root.left);
        if(!left){
            return false;
        }
        boolean mid = false;
        if(root.val>prev){
            mid = true;
        }else {
            return false;
        }
        prev = root.val;
        boolean right = isValidBST(root.right);
        if(!right){
            return false;
        }
        return left && mid && right;
    }
}
